Leetcode-29:Divide Two Integers

2018-01-14

问题描述：

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

我的答案

//Time Limit Exceeded
int divide(int dividend, int divisor) {
    int out = 0;
    //只有在dividend为Int_Max时会出错
    //因为Int_Max:2147483647,Int_Min:-2147483648,因为输入为int,最小为1，只有-1和Int_Min会出错
    if(dividend == INT_MIN){
        if(divisor == -1){
            return INT_MAX;
        }else{
            out++;
            dividend += abs(divisor);
        }
    }
    int absdividend = abs(dividend);
    int absdivisor = abs(divisor);
    bool positive = true;
    if((dividend>0&&divisor<0)||(dividend<0&&divisor>0)){
        positive = false;
    }
    while (absdividend>=absdivisor) {
        if(positive){
            absdividend -= absdivisor;
            if(out == INT_MAX){
                return INT_MAX;
            }
            out++;
        }else{
            absdividend -= absdivisor;
            if(out == INT_MIN){
                return INT_MAX;
            }
            out--;
        }
    }
    return out;
}

其他高效答案

//递归法
int divide(int dividend, int divisor) {
if (dividend == 0) return 0;
	if (divisor == 0) return INT_MAX;
	if (divisor == INT_MIN && dividend > divisor) return 0;
	int ret = 0;
	int accumulate = 0;
	if (dividend == INT_MIN) {
		if (divisor > 0){
			ret = divide(dividend + divisor, divisor);
			return ret - 1;
		}
		else {
			ret = divide(dividend - divisor, divisor);
			if (ret == INT_MAX) return INT_MAX;
			return ret + 1;
		}
	}	
	int sign = -1;
	if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) sign = 1;
	dividend = abs(dividend);
	divisor = abs(divisor);
	if (dividend - divisor < 0) return 0;
	accumulate = divisor;
	ret = 1;
	while (dividend - accumulate > accumulate){
		accumulate += accumulate;
		ret += ret;
	}
	int minus = divide(dividend - accumulate, divisor);
	if (sign > 0){
		return ret + minus;
	}
	else {
		return -ret - minus;
	}
}
//位运算
int divide(int dividend, int divisor) {
        int sign = (dividend ^ divisor) < 0 ? -1 : 1;
        long a = abs(long(dividend));
        long b = abs(long(divisor));
        
        int count = 1;
        long res = 0;
        
        while (b <= a) {
            long c = b;
            count = 1;
            while (c <= a) {
                res += count;
                a -= c;
                c <<= 1;
                count <<= 1;
            }
        }
        if (res > INT_MAX) return sign > 0 ? INT_MAX : INT_MIN;
        return res * sign;
}